//输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。 
//
// 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 
//
// 
//
// 示例 1: 
//
// 
//Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
//Output: [3,9,20,null,null,15,7]
// 
//
// 示例 2: 
//
// 
//Input: preorder = [-1], inorder = [-1]
//Output: [-1]
// 
//
// 
//
// 限制： 
//
// 0 <= 节点个数 <= 5000 
//
// 
//
// 注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-
//preorder-and-inorder-traversal/ 
// Related Topics 树 数组 哈希表 分治 二叉树 👍 655 👎 0

package com.cute.leetcode.editor.cn;
public class ZhongJianErChaShuLcof {
    public static void main(String[] args) {
        int[] preOrder = {1,2,4,8,9,5,3,6,7};
        int[] inorder = {8,4,9,2,5,1,6,3,7};
        new ZhongJianErChaShuLcof().new Solution().buildTree(preOrder, inorder);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     * 重构二叉树，切片就完了
     * 区间左闭右开
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        if (len == 0) return null;
        return ass(preorder, 0, len, inorder, 0, len);
    }

    /**
     * 必须对两个数组切片，一组start end 不现实
     * 不要贪少参数，有时就是需要多个参数才行
     */
    public TreeNode ass(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd){
        if (preBegin == preEnd) return null;
        int val = preorder[preBegin];
        TreeNode root = new TreeNode(val);
        if (inEnd - inBegin == 1) return root;//叶子节点的判断
        int index;
        for (index = inBegin; index < inEnd; index++) {
            if (inorder[index] == val) break;
        }
        int inLeftBegin = inBegin;
        int inLeftEnd = index;
        int inRightBegin = index + 1;
        int inRightEnd = inEnd;

        int preLeftBegin = preBegin + 1;
        int preLeftEnd = preLeftBegin + index - inLeftBegin;//根据长度切割
        int preRightBegin = preLeftEnd;
        int preRightEnd = preEnd;

        root.left = ass(preorder, preLeftBegin, preLeftEnd, inorder, inLeftBegin, inLeftEnd);
        root.right = ass(preorder, preRightBegin, preRightEnd, inorder, inRightBegin, inRightEnd);
        return root;

    }

}
//leetcode submit region end(Prohibit modification and deletion)
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}